import java.util.Arrays;

/**
 * 超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
 *
 * 给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
 *
 * 题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
 */
public class Test313 {
    public static void main(String[] args) {
        int[] nums = {2,3,7,13,17,23,31,41,43,47};
        int ret = nthSuperUglyNumber(44, nums);
        System.out.println(ret);
    }
    public static int nthSuperUglyNumber(int n, int[] primes) {
        int[] dp = new int[n+1];
        int[] primeIndex = new int[primes.length];
        Arrays.fill(primeIndex, 1);
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int max = Integer.MAX_VALUE;
            int minIndex = 0;
            for (int j = 0; j < primeIndex.length; j++) {
                if (dp[primeIndex[j]]*primes[j] < max){
                    if (dp[primeIndex[j]]*primes[j] == dp[i-1]){
                        if (dp[primeIndex[j]]*primes[j] == dp[i-1]){
                            primeIndex[j]++;
                            j = j-1;
                            continue;
                        }
                    }
                    max = dp[primeIndex[j]]*primes[j];
                    minIndex = j;
                }
            }
            primeIndex[minIndex]++;
            dp[i] = max;
        }
        return dp[n];
    }
}
